package 中等.贪心思想;

/**
 * 小写字符 的 数值 是它在字母表中的位置（从 1 开始），因此 a 的数值为 1 ，b 的数值为 2 ，c 的数值为 3 ，以此类推。
 * 字符串由若干小写字符组成，字符串的数值 为各字符的数值之和。例如，字符串 "abe" 的数值等于 1 + 2 + 5 = 8 。
 * 给你两个整数 n 和 k 。返回 长度 等于 n 且 数值 等于 k 的 字典序最小 的字符串。
 * 注意，如果字符串 x 在字典排序中位于 y 之前，就认为 x 字典序比 y 小，有以下两种情况：
 * x 是 y 的一个前缀；
 * 如果 i 是 x[i] != y[i] 的第一个位置，且 x[i] 在字母表中的位置比 y[i] 靠前。
 *  
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode.cn/problems/smallest-string-with-a-given-numeric-value
 */
public class 具有给定数值的最小字符串_1663 {

    public static void main(String[] args) {

        System.out.println(getSmallestString(1, 2));

    }

    /**
     * 贪心
     * 据观察，可以得到答案为 aaa... _ zzz...
     * 的格式，_ 的位置可以是 a-z 任意一个字符
     * 前面数字需要尽可能的小，后面的数字需要尽可能的大
     * 1，如果当前字符填 a 后面字符全部填 z , 可以满足 >=k
     * 的条件，那么当前字符填 a ，
     * 2，否则到达了分界处
     * 需要当前字符 + 26*(n-i) == k ，对26取模，填对应的字符
     * 3，剩下的字符全部填 z
     */
    public static String getSmallestString(int n, int k) {
        StringBuilder stringBuilder = new StringBuilder();
        for (int i = 1; i <= n; i++) {
            if (1 + 26 * (n - i) >= k) {
                stringBuilder.append('a');
                k--;
            } else {
                if (k % 26 != 0)
                    stringBuilder.append((char) ('a' + (k % 26) - 1));
                break;
            }
        }
        for (int i = stringBuilder.length() + 1; i <= n; i++) {
            stringBuilder.append('z');
        }

        return stringBuilder.toString();
    }

}
